package lcr;

public class Test0051 {

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(-2);
        TreeNode treeNode2 = new TreeNode(1);
        treeNode1.left = treeNode2;
        Solution0051_1 solution0051_1 = new Solution0051_1();
        System.out.println(solution0051_1.maxPathSum(treeNode1));
    }
}

class Solution0051_1 {

    int ans=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }

    public int dfs(TreeNode node){
        if (node==null) return Integer.MIN_VALUE;

        int left = dfs(node.left);
        int right = dfs(node.right);
        int val = node.val;

        int sum = val + Math.max(Math.max(left, 0), Math.max(right, 0));

        ans = Math.max(sum, ans);
        int a = val + Math.max(left, 0) + Math.max(right, 0);
        ans = Math.max(a, ans);

        return sum;
    }
}